package br.ufmg.vod.wbr.algorithims.betweness;

import br.ufmg.vod.collections.IntQueue;
import br.ufmg.vod.wbr.algorithims.bfs.BFSData;
import br.ufmg.vod.wbr.algorithims.bfs.FastBFS;
import br.ufmg.vod.wbr.api.Graph;

public class BetwenessBFS implements Runnable {
	
	int[] betwenessSum;
	int[] currentBetweness;
	private final Graph graph;
	
	public BetwenessBFS(Graph graph){
		this.graph = graph;
		this.betwenessSum = new int[graph.getNumVertex()];
		this.currentBetweness = new int[graph.getNumVertex()];
	}

	@Override
	public void run() {
		long start = System.currentTimeMillis();
		FastBFS bfsAlgorithm = new FastBFS(graph);
		for (int u = 0; u < graph.getNumVertex(); u++) {
			if(u%1024==0) System.out.printf("%s %.3f\n",u, (System.currentTimeMillis()-start)/1000f);
			bfsAlgorithm.bfsSingleVertex(u);
			BFSData data = bfsAlgorithm.getData();
			IntQueue visited =  data.visitedQueue;
			for (int i = visited.size()-1; i >= 0; i--) {
				int v = visited.peek(i);
				int pi = data.predecessor[v];
				if( pi != u ){
					currentBetweness[pi] += (1+currentBetweness[v]);
					betwenessSum[v]+=currentBetweness[v];
					currentBetweness[v]=0;
				}
			}
			bfsAlgorithm.clear();
		}
	}
	
	public double getBetweness(int vertex){
		return betwenessSum[vertex]/(((double)betwenessSum.length-1.0)*((double)betwenessSum.length-2.0));
	}

}
